Pac-Man!

Objective

The objective of this project was to create our own version of Pac-man, the iconic arcade game released by Bandai Namco Entertainment in the 1980s. While many facets of our project stayed true to the original version, we also augmented the game with features and minigames inspired by more modern video game titles to make it more fun.

Introduction

For our ECE 5725 final project, we created a replica of the classic arcade game, Pac-Man! The game runs on a Raspberry Pi 4, using a piTFT 2.8” LCD Touchscreen for graphics, and a four-directional joystick for input. We use the Pygame library to generate all of the animations. The nature of the game is identical to that of the original version originally released in arcades by Bandai Namco in the 1980s. In our version, the player uses the joystick to navigate the main menu and select different configurations of the game, including game modes and easter-egg features not available in the original 1980s version. During regular gameplay, the player uses the joystick to steer Pac-Man through a maze, collecting points and power-ups while avoiding the four ghosts. When the game is over, the user is brought back to the main menu where the game can be reconfigured and restarted.

Hardware Design

Our hardware design was fairly simple. The only two hardware components aside from the Raspberry Pi itself were the piTFT Touchscreen and the joystick. The joystick acts as four separate buttons, one for each direction: up, left, right, and down. Therefore, interfacing the joystick with the Raspberry Pi was as easy as configuring four separate tactile buttons. For safety, we decided to install external pull-up resistors, even though there are internal ones configurable on a per-pin basis inside the Raspberry Pi. Keeping the external resistors poses no harm to the system, and provides an additional buffer between the hardware and any electrical accidents that could damage the Raspberry Pi. The following images show the circuit diagram and final implementation of the joystick:

To test our hardware configuration, we created a python script that detects when the GPIO pins are pulled low (since we connected them in an active low configuration) and prints which button is pressed to the terminal. This also helped us to map which GPIO pins correspond to which direction. The joystick is used for both navigating the menu and controlling Pac-Man.

Software Design

The first phase revolved around generating the map. In particular, we had the goal of making the map generation process modular, so that in the future we could develop custom maps for the game without much difficulty. The framework we decided on was to load the map as a .csv file, where the contents or function of each cell is encoded by an integer. The following diagrams show the .csv encoding of the default Pac-Man map, as well as a list of the special cell encodings:

• game_logic.py → All of our backend game logic. This file contained all of the logical elements of the game like the map, the entities (ghosts and Pac-Man), and the scoreboard. Also included an abundance of helper functions related to entity navigation, collision.
• user_interface.py → All of our front-end functionality. This file contained all of the sub-routines that we use to erase and display elements on the screen. Functions from this file are used to render our game's menu, map, entities, and scoreboard.
• menu.py → The menu and its related functionality. This file contained
• keyboard_control.py → An implementation of keyboard input for the game. This file allowed us to test the game without access to the Raspberry Pi and the joystick, and significantly accelerated the debugging process.
• pacman.py → The main program file. This file was where the functionality from the above files was strung together to create Pac-Man.
• test_bfs.py → A test suite for our maze-searching implementation.

Map

The first phase revolved around generating the map. In particular, we had the goal of making the map generation process modular, so that in the future we could develop custom maps for the game without much difficulty. The framework we decided on was to load the map as a .csv file, where the contents or function of each cell is encoded by an integer. The following diagram shows the .csv encoding of the default Pac-Man map.

Here is a list of the encodings:

• 0 → Walls
• 1 → Dots
• 2 → Empty cells
• 3 → Power-ups
• 4 → Pac-Man's Spawn
• 5 → Teleport A
• 6 → Teleport B
• 7 → Ghost spawn
• 8 → Ghost pen
• 11 → Blinky's corner
• 12 → Pinky's corner
• 13 → Inky's corner
• 14 → Clyde's corner

To load the map, we import the .csv into a 2D list, and iterate through each element storing the locations of all our special cells, like teleports and entity spawn points. A single grid cell on our Pac-Map map corresponds to a 7x7 block of pixels on the piTFT display. By storing the pixel coordinates of the top left corner of our map, and the size of each cell, we can dynamically generate the entire map based on the contents of each cell. To draw a cookie, we draw a 3x3 pixel square centered in the middle of the grid cell. To draw a power cookie, we draw two rectangles of 3x5 and 5x3 overlaid on top of each other, which creates what appears to be a circle. The size and color differences were specifically tuned to help the player distinguish between the cookies and power cookies.

The most challenging part of displaying the map was to dynamically render the walls. The shape of each wall depends on which of its neighboring cells are walls. We implemented a system where we look at every wall's surrounding grid cells, to determine what shape the wall is meant to be. Our first implementation had a number of issues. First, we could not distinguish between concave and convex corners. Convex corners have two neighboring walls, but concave corners commonly have four. We fixed this issue by adding extra logic to distinguish between the two cases. Second, the boundary wall surrounding the maze was not being drawn, since its neighboring cells were out of bounds. We fixed this by treating cells outside the bounds of the maze as walls, so even in the edge cases surrounding the maze border, our dynamic generation algorithm still applies. Following our modular approach to the design, we have a parameter representing the size of the margin on either side of Pac-Man, so the width of the lanes in the maze can be changed without changing our entire implementation. During development, we unit tested the implementation by displaying each individual cell type, ensuring that each component could render properly before proceeding to the next.

Pac-Man

Using the information loaded from the .csv file, we give Pac-Man a pair of spawn coordinates. Identical to the original game, we start Pac-Man facing to the left. Also identical to the original game, Pac-Man stores the next direction he wants to turn in, and turns in that direction at the first valid opportunity. Each frame, Pac-Man moves a single pixel in the direction he is facing. When Pac-Man becomes grid aligned (centered on a grid cell), the game checks to see if the buffered next direction is valid (if there is not a wall in his path). If so, the current direction is updated to be the next direction. Otherwise, Pac-Man continues moving in his current direction until he makes a valid turn, or hits a wall. In order to test this, we randomized his movements, increased the FPS, and then let the game run for a significant amount of time to check if his movement patterns were legal.

Next, we added the ability to teleport from one side of the map to the other through the tunnels. The implementation of the teleports is quite simple. When Pac-Man reaches one of the teleports, we set his location to the other teleport. To test this, we modified the CSV and initial direction to have Pac-Man move directly into one of the teleports at the beginning of the program. After some errors, we added edge cases to compensate for out of bounds errors, stemming from the fact that Pac-Man is inherently leaving the maze when he's about to teleport.

To connect the joystick to Pac-Man, we used GPIO interrupts to update Pac-Man's next direction. This way, we wouldn't waste time polling unnecessarily. We configured four button interrupts, one for each direction on the joystick. Each interrupt sets Pac-Man's buffered direction. By separating Pac-Man's input from his movement, it allowed us to modify each implementation without needing to rework the entire system, and even gave way to additional input devices (a keyboard) later in the development process.

Animation

Our first implementation of animation was to redraw the entire map on every frame. This was a bit of a crude implementation, but ran fine on more powerful machines, such a laptop. This implementation was problematic when we transitioned to running on the Raspberry Pi and the piTFT. It turned out that we were overloading the frame buffer on the piTFT, causing significant slowdowns. To make things more efficient, we replaced this implementation that erases small sections of the maze surrounding each entity. This selective refresh method gave us a 20x speed up in how fast our frames were running, and eliminated the lag in the animation.

Since Pac-Man and the ghosts are based on the same Entity class, the drawing behavior is the same for both of them. We animate the entities by erasing five cells in a “+” shape centered on each entity, and redraw those cells with the contents stored in the map. We then redraw the entities at their new locations on top of the newly-redrawn cells. Implementing the animation like this means we draw roughly 25 cells per frame, instead of over 900 cells like we were doing in our original implementation

Ghosts

The second major milestone in the project was to implement a targeting algorithm for the ghosts to hunt Pac-Man. This is one area where our implementation and the original 1980s version differ. In the original game, the ghosts have a very simple navigation algorithm that allows them to lose track of Pac-Man in certain places. This gives way to deterministic behavior, ghost behavior exploits, and a variety of “hiding spots” in the maze where Pac-Man will never get found. Instead, we chose to equip each ghost with a BFS-based targeting algorithm that would allow it to hunt Pac-Man efficiently no matter where he is in the maze. The targeting algorithm was augmented with a few features that suited our purposes. First, the algorithm treats the two teleports as identical locations in the maze. The ghosts can therefore route through the teleport if it is the shortest path to Pac-Man. Second, the BFS algorithm forbids ghosts from taking a 180 degree turn. This means that if a route is found, but the ghost is moving in the wrong direction to take that route, the algorithm continues searching. We equipped the algorithm with a depth parameter, so that we could limit the ghosts ability to hunt globally throughout the maze, but elected not to use this feature in our final implementation.

Characteristic of the original Pac-Man, the ghosts in our game have three behavioral modes. The two main states that the ghosts revolve between are the “scatter” and “chase” modes. In “scatter” mode, the ghosts return to patrol their respective corners. In “chase” mode, the ghosts hunt after Pac-Man. When Pac-Man eats a power-up, the ghosts go into “frightened” mode, where they move randomly. The following diagram depicts each ghost's “home corner” on the default Pac-Man map:

Also characteristic of the original Pac-Man, we assigned each ghost its own unique targeting behavior. There are four ghosts in Pac-Man, distinguishable by their name and color: Blinky (red), Pinky (pink), Inky (cyan), and Clyde (orange). Here is an outline of each of their unique behaviors in our implementation of the game:

• Blinky has an aggressive movement pattern. He always takes the shortest possible path to Pac-Man. In scatter mode, Blinky moves to and then stays in the upper right corner of the map. Blinky activates at the very beginning of the game.
• Pinky follows an ambush-based movement pattern. He tries to cut off Pac-Man by knowing where Pac-Man is currently moving and then takes the shortest path to the nearest intersection ahead of Pac-Man. In scatter mode, Pinky moves to and then stays in the upper left hand corner of the map. Pinky activates after Pac-Man has eaten 5 dots.
• Inky also follows an ambush-based movement pattern. Pinky tries to cut off Pac-Man by knowing where Pac-Man is currently moving and then takes the shortest path to the cell that is two squares ahead of Pac-Man. In scatter mode, Inky moves to and stays in the bottom right hand corner of the map. Inky activates after Pac-Man has eaten 30 dots.
• Clyde follows a passive movement pattern. In chase mode, Clyde moves around the map randomly. In scatter mode, Clyde moves to and stays in the bottom left hand corner of the map. Clyde activates after Pac-Man has eaten 80 dots.

Winning and Losing

To keep our code modular, we determine the initial number of cookies when we load in the map. This way, as we clear each individual cookie, we can decrement our total until we reach 0. When this happens, we know that Pac-Man has finished the current level and we load Pac-Man into a new level that has been refilled with dots. When Pac-Man runs out of lives, the player is returned to the main menu.

Scoreboard

The scoreboard was the simplest feature to implement in our game. The scoreboard is printed in the top right corner of the piTFT screen, and displays the score, the number of lives, and the level. The number of lives is printed as a set of pygame rectangles in the same shape and color as Pac-Man. Every time Pac-Man dies, one of these rectangles disappears.

Menu

The menu is loaded from a .csv file that encodes the menu items, the options associated with each item, and the color associated with each piece of text. The user is able to cycle through the menu with either the joystick or the keyboard, where up and down inputs cycle through items on the menu, and side-to-side movements cycle through the options for that item. We also build debugging features into our menu, which saved us the time of rerunning the program whenever we wanted to activate or deactivate debugging features.

Extras

We added a few extras into our game that were not included in the original Pac-Man. We added the ability to configure the difficulty in the menu, as well as the number of lives Pac-Man starts with. We felt that these were features that are present in any modern video game, and that our Pac-Man implementation should therefore also include these features. We also took advantage of our versatile map generation algorithm to implement a custom map that we designed ourselves. We also implemented a “blind mode” where game elements outside of Pac-Man's immediate vicinity are invisible to him. This actually turned out to be the most fun game mode to play.

Results

For the most part, everything performed as planned. The only thing that didn't work as planned is that we didn't achieve as smooth of an animation as we originally wanted for moving entities on the PiTFT. This was due to us overfilling the frame buffer on the piTFT which is why the animation was a tad choppy on the TFT compared to when we were running on a monitor or a laptop. We were able to meet all of our original goals outlined in the description and even achieved more than we set out to do. People enjoy playing our game, and of course we do as well!

Conclusion

Overall everything worked. The only major hindrance that we had throughout this project is ensuring that we met our timing deadline for frame rate and didn't overfill the frame buffer. People were able to experience Pac-Man through a variety of modes including changing difficulty levels, and dealing with blind mode, which reduces vision of the map to a limited radius around Pac-Man. This shows that we were able to achieve all of our initial goals and more. The only aspects of the original game that we didn't replicate are fruit generation, and the actual shapes of the entities. We do think that these would all be feasible if given more time. However, something we discovered that is a problem that we can't seem to resolve is filling up the frame buffer on the piTFT. We determined that we were drawing too many objects to the piTFT display each frame, and in our testing we found that the only solution would be to draw less rectangles to the display, reducing the number of features. On a more expensive display with a slightly larger frame buffer, we would pretty easily have met this requirement.

During this project, we gained valuable experience in several skills. Navigating the filesystem and creating files on the command line gave us a good first look at working with the Linux kernel. Creating the python programs that ran the game including taking input from external hardware devices, as well as heavy use of the pygame environment, helped enhance our python programming ability. In addition, this project was extremely fun to work on, and of course it was fun to play as well!

Future Work

If we had more time to work on this project, we would have explored more opportunities to replicate the original graphics of the game. In our implementation, we treat the ghosts and Pac-Man as appropriately colored squares, but in the actual game, they have their own shapes and animations as they move (i.e. the classic Pac-Man eating the cookies). In addition, we would have looked into adding in the fruit items that appear in the original game, but since they aren't critical for the overall gameplay, we decided that it was an acceptable aspect to leave out in order to focus on features such as different ghost movements, the visuals of the map, and the menu.

Parts List

• Raspberry Pi 4
• piTFT Display
• Joystick
• Resistors and Wires
• Breadboard

All of our parts were provided cost-free by the ECE 5725 lab. Thank you to Professor Skovira for providing us with all of the materials, especially the joystick.

References

Pac-Man Ghost Behaviors
Pygame Documentation
RPi.GPIO Documentation

Code

Pac-Man Github Repository

Work Distribution

We worked together during and outside of our lab hours. We also discussed all of the major design decisions together. We worked together to develop the initial map generation and game logic. Individually, Sam handled the entire hardware design, including wiring the joystick and testing joystick control. Sam developed the code for joystick input, and the code for running on the piTFT. Sam was also responsible for configuring the colors and layout of the game, and was the reason why we were able to replicate the nostalgic and “retro” feel of the original Pac-Man. Sam also drafted an early version of the final report, and assembled all of the pictures and diagrams that are on this webpage. Chris worked on the software design, such as implementing and testing our targeting algorithm, integrating targeting with the entity movements, improving the efficiency of our drawings to meet frame requirements, as well as optimizing all of our implementations for modularity. In addition, Chris added all the additional features that weren’t originally planned such as blind mode, configurable difficulty, configurable number of lives, and more. Chris also revised the report and added sections to reflect the new features that didn’t exist at the time of the first version.